package com.promote.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName Intersect
 * Description 两个数组的交集
 * @Author LiZiHao
 * Date 2022/3/8 15:52
 * @Version 1.0
 **/
public class Intersect {

    /**
     * 先对两个数组进行排序，然后使用两个指针，分别指向两个数组开始的位置。
     *
     * 如果两个指针指向的值相同，说明这个值是他们的交集，就把这个值加入到集合list中，然后两个指针在分别往后移一步。
     * 如果两个指针指向的值不同，那么指向的值相对小的往后移一步，相对大的先不动，然后再比较
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1,int[] nums2) {

        //先对两个数组进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0,j = 0;

        List<Integer> list = new ArrayList<>();

        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            }

            else if (nums1[i]>nums2[j]) {
                j++;
            }

            else {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }

        //把list转为数组
        int index = 0;
        int[] res = new int[list.size()];
        for (int k = 0; k < list.size(); k++) {
            res[index++] = list.get(k);
        }
        return res;
    }
}
